#include <iostream>
#include <vector>
#include <string>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution 
{
public:
    void recursion(TreeNode * node, string path, vector<string> & result)
    {
        path += to_string(node->val);
        if(node->left == nullptr && node->right == nullptr)
        {
            result.push_back(path);
            return;
        }
        if(node->left != nullptr && node->right != nullptr)
        {
            recursion(node->left, path + "->", result);
            recursion(node->right, path + "->", result);
        }
        else if(node->left == nullptr)
        {
            recursion(node->right, path + "->", result);
        }
        else
        {
            recursion(node->left, path + "->", result);
        }
        return;
    }

    vector<string> binaryTreePaths(TreeNode* root) 
    {
       vector<string> result;
       if(root == nullptr)
       {
            return result;
       }
       string path;
       recursion(root, path, result);
       return result;
    }
};

// 辅助函数：创建二叉树节点
TreeNode* createNode(int val) {
    return new TreeNode(val);
}

// 辅助函数：释放二叉树内存
void deleteTree(TreeNode* root) {
    if (root == nullptr) return;
    deleteTree(root->left);
    deleteTree(root->right);
    delete root;
}

// 辅助函数：打印字符串向量
void printPaths(const vector<string>& paths) {
    cout << "[";
    for (int i = 0; i < paths.size(); i++) {
        cout << "\"" << paths[i] << "\"";
        if (i < paths.size() - 1) cout << ", ";
    }
    cout << "]" << endl;
}

int main() {
    Solution solution;
    
    cout << "=== LeetCode 257. 二叉树的所有路径 测试案例 ===" << endl;
    
    // 测试案例1: 示例1 - [1,2,3,null,5]
    cout << "\n测试案例1: [1,2,3,null,5]" << endl;
    TreeNode* root1 = createNode(1);
    root1->left = createNode(2);
    root1->right = createNode(3);
    root1->left->right = createNode(5);
    
    vector<string> result1 = solution.binaryTreePaths(root1);
    cout << "输入: [1,2,3,null,5]" << endl;
    cout << "输出: ";
    printPaths(result1);
    cout << "期望: [\"1->2->5\", \"1->3\"]" << endl;
    
    // 测试案例2: 示例2 - [1]
    cout << "\n测试案例2: [1]" << endl;
    TreeNode* root2 = createNode(1);
    
    vector<string> result2 = solution.binaryTreePaths(root2);
    cout << "输入: [1]" << endl;
    cout << "输出: ";
    printPaths(result2);
    cout << "期望: [\"1\"]" << endl;
    
    // 测试案例3: 空树 []
    cout << "\n测试案例3: []" << endl;
    TreeNode* root3 = nullptr;
    
    vector<string> result3 = solution.binaryTreePaths(root3);
    cout << "输入: []" << endl;
    cout << "输出: ";
    printPaths(result3);
    cout << "期望: []" << endl;
    
    // 测试案例4: 完全二叉树 [1,2,3,4,5,6,7]
    cout << "\n测试案例4: [1,2,3,4,5,6,7]" << endl;
    TreeNode* root4 = createNode(1);
    root4->left = createNode(2);
    root4->right = createNode(3);
    root4->left->left = createNode(4);
    root4->left->right = createNode(5);
    root4->right->left = createNode(6);
    root4->right->right = createNode(7);
    
    vector<string> result4 = solution.binaryTreePaths(root4);
    cout << "输入: [1,2,3,4,5,6,7]" << endl;
    cout << "输出: ";
    printPaths(result4);
    cout << "期望: [\"1->2->4\", \"1->2->5\", \"1->3->6\", \"1->3->7\"]" << endl;
    
    // 测试案例5: 只有左子树 [1,2,null,4]
    cout << "\n测试案例5: [1,2,null,4]" << endl;
    TreeNode* root5 = createNode(1);
    root5->left = createNode(2);
    root5->left->left = createNode(4);
    
    vector<string> result5 = solution.binaryTreePaths(root5);
    cout << "输入: [1,2,null,4]" << endl;
    cout << "输出: ";
    printPaths(result5);
    cout << "期望: [\"1->2->4\"]" << endl;
    
    // 测试案例6: 只有右子树 [1,null,3,null,7]
    cout << "\n测试案例6: [1,null,3,null,7]" << endl;
    TreeNode* root6 = createNode(1);
    root6->right = createNode(3);
    root6->right->right = createNode(7);
    
    vector<string> result6 = solution.binaryTreePaths(root6);
    cout << "输入: [1,null,3,null,7]" << endl;
    cout << "输出: ";
    printPaths(result6);
    cout << "期望: [\"1->3->7\"]" << endl;
    
    // 测试案例7: 不平衡树 [1,2,3,4,null,null,7,8]
    cout << "\n测试案例7: [1,2,3,4,null,null,7,8]" << endl;
    TreeNode* root7 = createNode(1);
    root7->left = createNode(2);
    root7->right = createNode(3);
    root7->left->left = createNode(4);
    root7->right->right = createNode(7);
    root7->left->left->left = createNode(8);
    
    vector<string> result7 = solution.binaryTreePaths(root7);
    cout << "输入: [1,2,3,4,null,null,7,8]" << endl;
    cout << "输出: ";
    printPaths(result7);
    cout << "期望: [\"1->2->4->8\", \"1->3->7\"]" << endl;
    
    // 释放内存
    deleteTree(root1);
    deleteTree(root2);
    // root3 已经是 nullptr，不需要释放
    deleteTree(root4);
    deleteTree(root5);
    deleteTree(root6);
    deleteTree(root7);
    
    cout << "\n=== 测试完成 ===" << endl;
    
    return 0;
}